/*
 * priorunqueue.cpp
 *
 *  Created on: 2011-5-26
 *      Author: chenl
 */

#include "priorunqueue.h"
#include "ps_error.h"
#include "common/common_magic.h"
#include "common/common_err.h"
#include "common/common_bit.h"
#include "task_wrapper.h"

CPrioRunQueue::CPrioRunQueue()
	: nr_running(0), nr_switching(0), nr_uninterruptible(0),
	  expired_timestamp(0), timestamp_last_tick(0), nr_switches(0), best_expired_prio(enmMaxPriority),
	  pActiveQueue(&taskQueue_[0]), pExpireQueue(&taskQueue_[1])
{
	memset(pActiveQueue->bitmap, 0, sizeof(pActiveQueue->bitmap));
	memset(pExpireQueue->bitmap, 0, sizeof(pExpireQueue->bitmap));
}

CPrioRunQueue::~CPrioRunQueue()
{
#ifdef DEBUG
	pActiveQueue = (RunQueue*)DEBUF_MEM_MAGIC;
	pExpireQueue = (RunQueue*)DEBUF_MEM_MAGIC;
#endif // DEBUG
}

int32_t CPrioRunQueue::Initialize()
{
	return S_OK;
}

int32_t CPrioRunQueue::InsertTask(CTask& task)
{
	if (0 > task.task.prio || enmMaxPriority <= task.task.prio)
	{
		return E_PS_INVALID_TASKPRIO;
	}
	assert(NULL != pActiveQueue);
	int32_t ret = pActiveQueue->queue[task.task.prio].InsertTask(task);
	if (0 <= ret)
	{
		SET_BIT(pActiveQueue->bitmap[task.task.prio / 32], task.task.prio % 32);
		++pActiveQueue->nr_active;
		task.task.array = pActiveQueue;
	}
	++nr_running;
	return ret;
}

int32_t CPrioRunQueue::DeleteTask(CTask& task)
{
	if (0 > task.task.prio || enmMaxPriority <= task.task.prio)
	{
		return E_PS_INVALID_TASKPRIO;
	}
	assert(NULL != pActiveQueue);
	task.task.array = NULL;
	int32_t ret = pActiveQueue->queue[task.task.prio].DeleteTask(task);
	if (0 <= ret)
	{
		if (pActiveQueue->queue[task.task.prio].IsEmtpy())
		{
			CLEAR_BIT(pActiveQueue->bitmap[task.task.prio / 32], task.task.prio % 32);
		}
		--pActiveQueue->nr_active;
		--nr_running;
		return ret;
	}
	assert(NULL != pExpireQueue);
	ret = pExpireQueue->queue[task.task.prio].DeleteTask(task);
	if (0 <= ret)
	{
		if (pExpireQueue->queue[task.task.prio].IsEmtpy())
		{
			CLEAR_BIT(pExpireQueue->bitmap[task.task.prio / 32], task.task.prio % 32);
		}
		--pExpireQueue->nr_active;
		--nr_running;
		return ret;
	}
	return S_OK;
}

bool CPrioRunQueue::IsTaskOnQueue(const CTask& task)
{
	CTaskQueue::TaskQueueItr itr;
	CTaskQueue	queue;
	bool result = S_OK == SearchTask(task, *pActiveQueue, itr, queue) ? true : false;
	if(!result)
	{
		result = S_OK == SearchTask(task, *pExpireQueue, itr, queue) ? true : false;
	}
	return result;
}

int32_t CPrioRunQueue::SwapTask(CTaskQueue::TaskQueueItr itr, CTaskQueue* pFromQueue, CTaskQueue* pToQueue)
{
	assert (NULL != pFromQueue);
	assert (NULL != pToQueue);
	if (NULL == *itr)
	{
		return E_NULLPOINTER;
	}
	if (pFromQueue->IsEmtpy())
	{
		return E_QUEUEISEMPTY;
	}
	pToQueue->taskQueue.push_back(*itr);
	pFromQueue->taskQueue.erase(itr);
	return S_OK;
}

int32_t CPrioRunQueue::FindTask(const CTask& task, RunQueue& runqueue, CTaskQueue::TaskQueueItr& itr, CTaskQueue& queue)
{
	if (0 > task.task.prio || enmMaxPriority <= task.task.prio)
	{
		return E_PS_INVALID_TASKPRIO;
	}
	queue = runqueue.queue[task.task.prio];
	itr = queue.FindTask(task);
	if (queue.taskQueue.end() == itr)
	{
		return E_PS_TASKNOTFOUND;
	}
	return S_OK;
}

int32_t CPrioRunQueue::SearchTask(const CTask& task, RunQueue& runqueue, CTaskQueue::TaskQueueItr& itr, CTaskQueue& queue)
{
	int32_t ret = S_OK;
	for (int i = 0; i < enmMaxPriority; ++i)
	{
		ret = FindTask(task, runqueue, itr, queue);
		if (0 <= ret)
			break;
	}
	return ret;
}

CTask* CPrioRunQueue::FirstTask(RunQueue& queue)
{
	int i = 0, j = 0;
	for(; i < enmBitMapSize; ++i)
	{
		if (0 == queue.bitmap[i])
			++j;
	}
	if (enmBitMapSize <= j)
	{
		return NULL;
	}
	int idx = sched_find_first_bit(queue.bitmap);
	CTask* pTask = queue.queue[idx].FirstTask();
	assert(NULL != pTask);
	return pTask;
}

CTask* CPrioRunQueue::NextTask(RunQueue& runqueue, CTask& oldTask)
{
	CTaskQueue::TaskQueueItr itr;
	CTaskQueue	queue;
	CTask* pTask = NULL;
	int prio = oldTask.task.prio;
	int idx = prio;

	int32_t ret = FindTask(oldTask, runqueue, itr, queue);
	if (0 > ret)
	{
		return NULL;
	}
	pTask = queue.NextTask(oldTask);
	if (NULL != pTask)
	{
		return pTask;
	}

	while (enmBitMapSize > idx / 32)
	{
		if(0 != runqueue.bitmap[idx / 32])
		{
			while (++idx < enmMaxPriority && NULL == pTask)
			{
				pTask = runqueue.queue[idx].FirstTask();
			}
			if (NULL != pTask)
			{
				return pTask;
			}
		}
		else
			idx = idx + 32 - (idx + 32) % 32;
	}

	return pTask;
}

CTask* CPrioRunQueue::FirstTask()
{
	CTask *pTask = NULL;
	pTask = FirstTask(*pActiveQueue);
	if (NULL != pTask)
	{
		return pTask;
	}
	pTask = FirstTask(*pExpireQueue);
	return pTask;
}

CTask* CPrioRunQueue::NextTask(CTask& oldTask)
{
	static unsigned long count = 1;

	if (count >= nr_running)
	{
		count = 1;
		return NULL;
	}

	CTask *pTask = NULL;
	pTask = NextTask(*pActiveQueue, oldTask);
	if (NULL != pTask)
	{
		++count;
		return pTask;
	}
	pTask = NextTask(*pExpireQueue, oldTask);
	if (NULL != pTask)
	{
		++count;
		return pTask;
	}
	pTask = FirstTask(*pExpireQueue);
	if (NULL != pTask)
	{
		++count;
		return pTask;
	}
	else
	{
		count = 1;
	}
	return pTask;
}

int32_t CPrioRunQueue::SwapOutTask(CTask& task)
{
	int32_t ret = pActiveQueue->queue[task.task.prio].DeleteTask(task);
	assert(0 <= ret);
	if (0 > ret)
	{
		return ret;
	}
	ret = pExpireQueue->queue[task.task.prio].InsertTask(task);
	assert(0 <= ret);
	return ret;
}
